﻿/*837. 连通块中点的数量

给定一个包含 n个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m个操作，操作共有三种：
C a b，在点 a和点 b之间连一条边，a和 b可能相等；
Q1 a b，询问点 a和点 b是否在同一个连通块中，a和 b可能相等；
Q2 a，询问点 a所在连通块中点的数量；

输入格式
第一行输入整数 n和 m
接下来 m行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式
对于每个询问指令 Q1 a b，如果 a和 b在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3*/

#include<iostream>
using namespace std;

const int N = 100010;
int p[N], sz[N]; //sz:size[]
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n, m, a, b;
    cin >> n >> m;
    char op[3];
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        sz[i] = 1;//每个节点初始size为1
    }

    while (m--)
    {
        cin >> op;

        if (op[0] == 'C') //if(op[0]=="C")  
        {
            cin >> a >> b;
            if (find(a) != find(b))
            {
                sz[find(a)] += sz[find(b)]; //这个书写格式：size[find(a)]
                p[find(b)] = find(a);
                //这两行顺序不能变，而且必须一致，都加在y里的话，p[x]=y,y就是父亲
            }
        }
        else if (op[1] == '1')//(op[0]=="Q1"') 
        {
            cin >> a >> b;
            if (find(a) == find(b))    cout << "Yes" << endl;
            else    cout << "No" << endl;
        }
        else
        {
            cin >> a;
            cout << sz[find(a)] << endl;
        }
    }
}

/*总结：
1. sz[find(a)] += sz[find(b)]; 
   p[find(b)] = find(a);
  这两行顺序不能变，而且必须一致，都加在y里的话，p[x]=y,y就是父亲
2.char op[3];存的是这样的：
  输入C：op[0]=C
  输入Q1：op[0]=Q  op[1]=1
  输入Q2：op[0]=Q  op[1]=2
  对于输入的字符串长度限制为3，可访问0-2的下标，op[i]识别一个char
  
3.c++ 中的char *arr[] 和string arr的末尾
在c/c++中，字符数组表示字符串时，当在数组中间添加‘\0’时表示字符串结束，输出的是字符数组中‘\0’前面的字符组成的字符串
如 char p[]="abcdefghi";  p[3]=‘\0’;   cout<<p；  结果是abc
当定义string arr="abcdefg"时，若在中间某一位置换成'\0'，则只是将该位置的字符替换成'\0'，而不是表示字符串结束
如 string arr="abcdefg";  arr[3]='\0';  cout<<arr;  结果为abc efg;
注意：判断字符串数组的长度用sizeof(arr)/sizeod(arr[0]);
*/

//这个题吧，看似是图，但是实际还是集合，用并交集解决
